"""
左偏树静态结构

测试链接: https://www.luogu.com.cn/problem/P3377
"""

MAXN = 100001

# 从1开始，0位置代表空节点
# nums: value
# left,right: 左，右节点。
# dist: 离开当前节点后，到达空节点的最短距离
nums = [0] * MAXN
left = [0] * MAXN
right = [0] * MAXN
dist = [0] * MAXN
father = [0] * MAXN  # 并查集 father 结构，方便快速找头


def init(n):
    dist[0] = -1
    for i in range(1, n + 1):
        left[i] = right[i] = dist[i] = 0
        father[i] = i


# 并查集的find 找头
def find(x):
    if x != father[x]:
        father[x] = find(father[x])
    return father[x]


# 合并两个堆
def merge(x, y):
    if x == 0 or y == 0:  # 如果有一个为空节点，直接挂， 两个都为空就啥都不做
        return x + y
    # if nums[x] < nums[y]:
    # 0. 找头[实现的小顶堆]。题目要求，两个子堆(子树)，根节点相同，下标小的，当新头
    if nums[x] > nums[y] or (nums[x] == nums[y] and x > y):
        x, y = y, x
    # 1. 在右树上进行合并
    right[x] = merge(right[x], y)

    # 2. 合并后，让左树的 dist 要 >= 右树的dist。 否则就直接交换两树
    if dist[left[x]] < dist[right[x]]:
        left[x], right[x] = right[x], left[x]

    # 3. 修正我的dist，右树dist肯定<= 左树的，所有我从右边走总是<= 从左边走到空的距离
    dist[x] = dist[right[x]] + 1
    # 维护并查集的father信息
    father[left[x]] = father[right[x]] = x
    return x


# 删除当前堆的根节点
def pop(x):
    father[left[x]] = left[x]
    father[right[x]] = right[x]

    # 清空我的信息, 不进行真实删除
    # 但是并查集的信息要维护：可能之前有节点直接find，路径压缩，直连的我，所以要继续维护这个并查集的信息
    father[x] = merge(left[x], right[x])
    left[x] = right[x] = dist[x] = 0
    return father[x]


# 测试题目相关输入输出
import sys

n, m = map(int, sys.stdin.readline().split())
init(n)
nums[1:n+1] = list(map(int, sys.stdin.readline().split()))
res = []
for _ in range(m):
    ops = list(map(int, sys.stdin.readline().split()))
    if ops[0] == 1:
        if nums[ops[1]] == -1 or nums[ops[2]] == -1:
            continue
        root_a, root_b = find(ops[1]), find(ops[2])
        # 如果两个堆在一个堆里，或其中至少一个已经被删除了
        if root_a != root_b:
            merge(root_a, root_b)
    else:
        if nums[ops[1]] == -1:
            res.append("-1")
        else:
            root = find(ops[1])
            res.append(str(nums[root]))
            pop(root)
            nums[root] = -1
sys.stdout.write("\n".join(res))
